Search Results

Documents authored by Kontogiannis, Spyros

Document
DOI: 10.4230/OASIcs.ATMOS.2022.12
REX: A Realistic Time-Dependent Model for Multimodal Public Transport

Authors: Spyros Kontogiannis, Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos, and Christos Zaroliagis

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.
Cite as

Spyros Kontogiannis, Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos, and Christos Zaroliagis. REX: A Realistic Time-Dependent Model for Multimodal Public Transport. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2022.12,
  author =	{Kontogiannis, Spyros and Machaira, Paraskevi-Maria-Malevi and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{REX: A Realistic Time-Dependent Model for Multimodal Public Transport}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{12:1--12:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.12},
  URN =		{urn:nbn:de:0030-drops-171164},
  doi =		{10.4230/OASIcs.ATMOS.2022.12},
  annote =	{Keywords: multimodal journey planning, REX model, TRIPLA query algorithm, schedule-based timetables}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.8
Time-Dependent Alternative Route Planning

Authors: Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches. In particular, the entire alternative graph can be computed in less than 0.384sec for the road network of Germany, and in less than 1.24sec for that of Europe. Our approach provides also "quick-and-dirty" results of decent quality, in about 1/300 of the above mentioned query times for continental-size instances.
Cite as

Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis. Time-Dependent Alternative Route Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2020.8,
  author =	{Kontogiannis, Spyros and Paraskevopoulos, Andreas and Zaroliagis, Christos D.},
  title =	{{Time-Dependent Alternative Route Planning}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{8:1--8:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.8},
  URN =		{urn:nbn:de:0030-drops-131441},
  doi =		{10.4230/OASIcs.ATMOS.2020.8},
  annote =	{Keywords: time-dependent shortest path, alternative routes, travel-time oracle, plateau and penalty methods}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.9
Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations

Authors: Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, and Christos Zaroliagis

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
We aim at exploiting parallelism in shared-memory multiprocessing systems, in order to speed up the execution time with as small redundancy in work as possible, for an elementary task that comes up frequently as a subroutine in the daily maintenance of large-scale time-dependent graphs representing real-world relationships or technological networks: the many-to-all time-dependent shortest paths (MATDSP) problem. MATDSP requires the computation of one time-dependent shortest-path tree (TDSPT) per origin-vertex and departure-time, from an arbitrary collection of pairs of origins and departure-times, towards all reachable destinations in the graph. Our goal is to explore the potential and highlight the limitations of amorphous data parallelism, when dealing with MATDSP in multicore computing environments with a given amount of processing elements and a shared memory to exploit. Apart from speeding-up execution time, consumption of resources (and energy) is also critical. Therefore, we aim at limiting the work overhead for solving a MATDSP instance, as measured by the overall number of arc relaxations in shortest-path computations, while trying to minimize the overall execution time. Towards this direction, we provide several algorithmic engineering interventions for solving MATDSP concerning: (i) the compact representation of the instance; (ii) the choice and the improvement of the time-dependent single-source shortest path algorithm that is used as a subroutine; (iii) the way according to which the overall work is allocated to the processing elements; (iv) the adoption of the amorphous data parallelism rationale, in order to avoid costly synchronization among the processing elements while doing their own part of the work. Our experimental evaluations, both on real-world and on synthetic benchmark instances of time-dependent road networks, provide insight how one should organize heavy MATDSP computations, depending on the application scenario. This insight is in some cases rather unexpected. For instance, it is not always the case that pure data parallelism (among otherwise totally independent processors) is the best choice for minimizing execution times. In certain cases it may be worthwhile to limit the level of data parallelism in favor of algorithmic parallelism, in order to achieve more efficient MATDSP computations.
Cite as

Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, and Christos Zaroliagis. Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2019.9,
  author =	{Kontogiannis, Spyros and Papadopoulos, Anastasios and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{9:1--9:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.9},
  URN =		{urn:nbn:de:0030-drops-114210},
  doi =		{10.4230/OASIcs.ATMOS.2019.9},
  annote =	{Keywords: amorphous data parallelism, delta-stepping algorithm, travel-time oracle, many-to-all shortest paths, time-dependent road networks}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.4
Improved Oracles for Time-Dependent Road Networks

Authors: Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden of landmark-based oracles (the large preprocessing requirements), CFLAT is extensively engineered. A thorough experimental evaluation on two real-world benchmark instances shows that CFLAT achieves a significant improvement on preprocessing, approximation guarantees and query-times, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.
Cite as

Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2017.4,
  author =	{Kontogiannis, Spyros and Papastavrou, Georgia and Paraskevopoulos, Andreas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Improved Oracles for Time-Dependent Road Networks}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.4},
  URN =		{urn:nbn:de:0030-drops-78954},
  doi =		{10.4230/OASIcs.ATMOS.2017.4},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.47
Hierarchical Time-Dependent Oracles

Authors: Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study networks obeying time-dependent min-cost path metrics, and present novel oracles for them which provably achieve two unique features: (i) subquadratic preprocessing time and space, independent of the metric’s amount of disconcavity; (ii) sublinear query time, in either the network size or the actual Dijkstra-Rank of the query at hand.
Cite as

Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis. Hierarchical Time-Dependent Oracles. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:LIPIcs.ISAAC.2016.47,
  author =	{Kontogiannis, Spyros and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Hierarchical Time-Dependent Oracles}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.47},
  URN =		{urn:nbn:de:0030-drops-68170},
  doi =		{10.4230/LIPIcs.ISAAC.2016.47},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2011
OASIcs, Volume 20, ATMOS'11, Complete Volume

Authors: Alberto Caprara and Spyros Kontogiannis

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
OASIcs, Volume 20, ATMOS'11, Complete Volume
Cite as

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{caprara_et_al:OASIcs.ATMOS.2011,
  title =	{{OASIcs, Volume 20, ATMOS'11, Complete Volume}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011},
  URN =		{urn:nbn:de:0030-drops-35824},
  doi =		{10.4230/OASIcs.ATMOS.2011},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2011.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Alberto Caprara and Spyros Kontogiannis

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Frontmatter, Table of contents, Preface, Workshop Organization
Cite as

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. i-ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{caprara_et_al:OASIcs.ATMOS.2011.i,
  author =	{Caprara, Alberto and Kontogiannis, Spyros},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--ix},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.i},
  URN =		{urn:nbn:de:0030-drops-32618},
  doi =		{10.4230/OASIcs.ATMOS.2011.i},
  annote =	{Keywords: Frontmatter, Table of contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1581
Robust Line Planning under Unknown Incentives and Elasticity of Frequencies

Authors: Spyros Kontogiannis and Christos Zaroliagis

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
The problem of robust line planning requests for a set of origin-destination paths (lines) along with their traffic rates (frequencies) in an underlying railway network infrastructure, which are robust to fluctuations of real-time parameters of the solution. In this work, we investigate a variant of robust line planning stemming from recent regulations in the railway sector that introduce competition and free railway markets, and set up a new application scenario: there is a (potentially large) number of line operators that have their lines fixed and operate as competing entities struggling to exploit the underlying network infrastructure via frequency requests, while the management of the infrastructure itself remains the responsibility of a single (typically governmental) entity, the network operator. The line operators are typically unwilling to reveal their true incentives. Nevertheless, the network operator would like to ensure a fair (or, socially optimal) usage of the infrastructure, e.g., by maximizing the (unknown to him) aggregate incentives of the line operators. We show that this can be accomplished in certain situations via a (possibly anonymous) incentive- compatible pricing scheme for the usage of the shared resources, that is robust against the unknown incentives and the changes in the demands of the entities. This brings up a new notion of robustness, which we call incentive-compatible robustness, that considers as robustness of the system its tolerance to the entities' unknown incentives and elasticity of demands, aiming at an eventual stabilization to an equilibrium point that is as close as possible to the social optimum.
Cite as

Spyros Kontogiannis and Christos Zaroliagis. Robust Line Planning under Unknown Incentives and Elasticity of Frequencies. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2008.1581,
  author =	{Kontogiannis, Spyros and Zaroliagis, Christos},
  title =	{{Robust Line Planning under Unknown Incentives and Elasticity of Frequencies}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1581},
  URN =		{urn:nbn:de:0030-drops-15813},
  doi =		{10.4230/OASIcs.ATMOS.2008.1581},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact